home *** CD-ROM | disk | FTP | other *** search
/ Qoole for Quake / Qoole for Quake (USA) / Qoole for Quake (USA).bin / Tutorial / HTML / QUBE.ZIP / SRC / REGION.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-11-05  |  9.5 KB  |  514 lines
  1. /* region.h */
  2.  
  3. #include "bsp5.h"
  4.  
  5. /*
  6.  
  7. input
  8. -----
  9. vertexes
  10. edges
  11. faces
  12.  
  13. output
  14. ------
  15. smaller set of vertexes
  16. smaller set of edges
  17. regions
  18. ? triangulated regions
  19. face to region mapping numbers
  20.  
  21. */
  22.  
  23. #define    MAX_EDGES_IN_REGION    32
  24.  
  25. int        firstedge;
  26.  
  27. vec3_t    region_mins, region_maxs;
  28.  
  29. void AddPointToRegion (vec3_t p)
  30. {
  31.     int        i;
  32.     
  33.     for (i=0 ; i<3 ; i++)
  34.     {
  35.         if (p[i] < region_mins[i])
  36.             region_mins[i] = p[i];
  37.         if (p[i] > region_maxs[i])
  38.             region_maxs[i] = p[i];
  39.     }    
  40. }
  41.  
  42. void ClearRegionSize (void)
  43. {
  44.     region_mins[0] = region_mins[1] = region_mins[2] = 9999;
  45.     region_maxs[0] = region_maxs[1] = region_maxs[2] = -9999;
  46. }
  47.  
  48. void AddFaceToRegionSize (face_t *f)
  49. {
  50.     int        i;
  51.  
  52.     for (i=0 ; i<f->numpoints ; i++)
  53.         AddPointToRegion (f->pts[i]);
  54. }
  55.  
  56. /*
  57. ==============
  58. CanJoinFaces
  59. ==============
  60. */
  61. qboolean CanJoinFaces (face_t *f, face_t *f2)
  62. {
  63.     vec3_t        oldmins, oldmaxs;
  64.     int            i;
  65.  
  66.     if (f2->planenum != f->planenum
  67.     || f2->planeside != f->planeside
  68.     || f2->texturenum != f->texturenum)
  69.         return false;
  70.     if (f2->outputnumber != -1)
  71.         return false;
  72.     if (f2->contents[0] != f->contents[0])
  73.     {    /* does this ever happen? they shouldn't share. */
  74.         ShowTempEntry("CanJoinFaces: edge with different contents");
  75.         return false;
  76.     }
  77.     
  78. /* check size constraints */
  79.     if ( ! (texinfo[f->texturenum].flags & TEX_SPECIAL) )
  80.     {    
  81.         VectorCopy (region_mins, oldmins);
  82.         VectorCopy (region_maxs, oldmaxs);
  83.         AddFaceToRegionSize (f2);
  84.         for (i=0 ; i<3 ; i++)
  85.         {
  86.             if (region_maxs[i] - region_mins[i] > 240)
  87.             {
  88.                 VectorCopy (oldmins, region_mins);
  89.                 VectorCopy (oldmaxs, region_maxs);
  90.                 return false;
  91.             }
  92.         }
  93.     }
  94.     else
  95.     {
  96.         if (numsurfedges - firstedge + f2->numpoints > MAX_EDGES_IN_REGION)
  97.             return false;        /* a huge water or sky polygon */
  98.     }
  99.     
  100. /* check edge count constraints */
  101.     return true;
  102. }
  103.  
  104.  
  105. /*
  106. ==============
  107. RecursiveGrowRegion
  108. ==============
  109. */
  110. void RecursiveGrowRegion (dface_t *r, face_t *f)
  111. {
  112.     int        e;
  113.     face_t    *f2;
  114.     int        i;
  115.     
  116.     if (f->outputnumber == numfaces)
  117.         return;
  118.  
  119.     if (f->outputnumber != -1)
  120.         Error ("RecursiveGrowRegion: region collision");
  121.     f->outputnumber = numfaces;
  122.     
  123. /* add edges     */
  124.     for (i=0 ; i<f->numpoints ; i++)
  125.     {
  126.         e = f->edges[i];
  127.         if (!edgefaces[abs(e)][0])
  128.             continue;    /* edge has allready been removed */
  129.         if (e > 0)
  130.             f2 = edgefaces[e][1];
  131.         else
  132.             f2 = edgefaces[-e][0];
  133.         if (f2 && f2->outputnumber == numfaces)
  134.         {
  135.             edgefaces[abs(e)][0] = NULL;
  136.             edgefaces[abs(e)][1] = NULL;
  137.             continue;    /* allready merged */
  138.         }
  139.         if (f2 && CanJoinFaces (f, f2))
  140.         {    /* remove the edge and merge the faces */
  141.             edgefaces[abs(e)][0] = NULL;
  142.             edgefaces[abs(e)][1] = NULL;
  143.             RecursiveGrowRegion (r, f2);
  144.         }
  145.         else
  146.         {
  147.         /* emit a surfedge */
  148.             if (numsurfedges == MAX_MAP_SURFEDGES)
  149.                 Error ("numsurfedges == MAX_MAP_SURFEDGES");
  150.             dsurfedges[numsurfedges] = e;
  151.             numsurfedges++;
  152.         }
  153.     }
  154.  
  155. }
  156.  
  157. void PrintDface (int f)
  158. {    /* for debugging */
  159.     dface_t    *df;
  160.     dedge_t    *e;
  161.     int        i, n;
  162.     
  163.     df = &dfaces[f];
  164.     for (i=0 ; i<df->numedges ; i++)
  165.     {
  166.         n = dsurfedges[df->firstedge+i];
  167.         e = &dedges[abs(n)];
  168.         if (n < 0)
  169.                         printf ("%5i  =  %5i : %5i\n", n, e->v[1], e->v[0]);
  170.         else
  171.             printf ("%5i  =  %5i : %5i\n", n, e->v[0], e->v[1]);
  172.     }
  173. }
  174.  
  175. void FindVertexUse (int v)
  176. {    /* for debugging */
  177.     int        i, j, n;
  178.     dface_t    *df;
  179.     dedge_t    *e;
  180.     
  181.     for (i=firstmodelface ; i<numfaces ; i++)
  182.     {
  183.         df = &dfaces[i];
  184.         for (j=0 ; j<df->numedges ; j++)
  185.         {
  186.             n = dsurfedges[df->firstedge+j];
  187.             e = &dedges[abs(n)];
  188.             if (e->v[0] == v || e->v[1] == v)
  189.             {
  190.                 printf ("on face %i\n", i);
  191.                 break;
  192.             }
  193.         }
  194.     }
  195. }
  196.  
  197. void FindEdgeUse (int v)
  198. {    /* for debugging */
  199.     int        i, j, n;
  200.     dface_t    *df;
  201.     
  202.     for (i=firstmodelface ; i<numfaces ; i++)
  203.     {
  204.         df = &dfaces[i];
  205.         for (j=0 ; j<df->numedges ; j++)
  206.         {
  207.             n = dsurfedges[df->firstedge+j];
  208.             if (n == v || -n == v)
  209.             {
  210.                 printf ("on face %i\n", i);
  211.                 break;
  212.             }
  213.         }
  214.     }
  215. }
  216.  
  217. /*
  218. ================
  219. HealEdges
  220.  
  221. Extends e1 so that it goes all the way to e2, and removes all references
  222. to e2
  223. ================
  224. */
  225. int        edgemapping[MAX_MAP_EDGES];
  226. void HealEdges (int e1, int e2)
  227. {
  228.     int        i, j, n, saved;
  229.     dface_t    *df;
  230.     dedge_t    *ed, *ed2;
  231.     vec3_t    v1, v2;
  232.     dface_t    *found[2];
  233.     int        foundj[2];
  234.  
  235. return;    
  236.     e1 = edgemapping[e1];
  237.     e2 = edgemapping[e2];
  238.  
  239. /* extend e1 to e2 */
  240.     ed = &dedges[e1];
  241.     ed2 = &dedges[e2];
  242.     VectorSubtract (dvertexes[ed->v[1]].point, dvertexes[ed->v[0]].point, v1);
  243.     VectorNormalize (v1);
  244.     
  245.     if (ed->v[0] == ed2->v[0])
  246.         ed->v[0] = ed2->v[1];
  247.     else if (ed->v[0] == ed2->v[1])
  248.         ed->v[0] = ed2->v[0];
  249.     else if (ed->v[1] == ed2->v[0])
  250.         ed->v[1] = ed2->v[1];
  251.     else if (ed->v[1] == ed2->v[1])
  252.         ed->v[1] = ed2->v[0];
  253.     else
  254.         Error ("HealEdges: edges don't meet");
  255.  
  256.     VectorSubtract (dvertexes[ed->v[1]].point, dvertexes[ed->v[0]].point, v2);
  257.     VectorNormalize (v2);
  258.     
  259.     if (!VectorCompare (v1, v2))
  260.         Error ("HealEdges: edges not colinear");
  261.  
  262.     edgemapping[e2] = e1;
  263.     saved = 0;
  264.     
  265. /* remove all uses of e2 */
  266.     for (i=firstmodelface ; i<numfaces ; i++)
  267.     {
  268.         df = &dfaces[i];
  269.         for (j=0 ; j<df->numedges ; j++)
  270.         {
  271.             n = dsurfedges[df->firstedge+j];
  272.             if (n == e2 || n == -e2)
  273.             {
  274.                 found[saved] = df;
  275.                 foundj[saved] = j;
  276.                 saved++;
  277.                 break;
  278.             }
  279.         }
  280.     }
  281.     
  282.     if (saved != 2) {
  283.         ShowWarningEntry("Didn't find both faces for a saved edge.");
  284.         sleep(1);
  285.         }
  286.         else
  287.     {
  288.         for (i=0 ; i<2 ; i++)
  289.         {    /* remove this edge */
  290.             df = found[i];
  291.             j = foundj[i];
  292.             for (j++ ; j<df->numedges ; j++)
  293.                 dsurfedges[df->firstedge+j-1] =
  294.                 dsurfedges[df->firstedge+j];
  295.             dsurfedges[df->firstedge+j-1] = 0;
  296.             df->numedges--;
  297.         }
  298.  
  299.  
  300.         edgefaces[e2][0] = edgefaces[e2][1] = NULL;
  301.     }
  302. }
  303.  
  304. typedef struct
  305. {
  306.     int        numedges;
  307.     int        edges[2];
  308. } checkpoint_t;
  309.  
  310. checkpoint_t    checkpoints[MAX_MAP_VERTS];
  311.  
  312. /*
  313. ==============
  314. RemoveColinearEdges
  315. ==============
  316. */
  317. void RemoveColinearEdges (void)
  318. {
  319.     int        i,j, v;
  320.     int        c0, c1, c2, c3;
  321.     checkpoint_t    *cp;
  322.     
  323. /* no edges remapped yet */
  324.     for (i=0 ; i<numedges ; i++)
  325.         edgemapping[i] = i;
  326.         
  327. /* find vertexes that only have two edges */
  328.     memset (checkpoints, 0, sizeof(checkpoints));
  329.     
  330.     for (i=firstmodeledge ; i<numedges ; i++)
  331.     {
  332.         if (!edgefaces[i][0])
  333.             continue;        /* removed */
  334.         for (j=0 ; j<2 ; j++)
  335.         {
  336.             v = dedges[i].v[j];
  337.             cp = &checkpoints[v];
  338.             if (cp->numedges<2)
  339.                 cp->edges[cp->numedges] = i;
  340.             cp->numedges++;
  341.         }
  342.     }
  343.     
  344. /* if a vertex only has two edges and they are colinear, it can be removed */
  345.     c0 = c1 = c2 = c3 = 0;
  346.     
  347.     for (i=0 ; i<numvertexes ; i++)
  348.     {
  349.         cp = &checkpoints[i];
  350.         switch (cp->numedges)
  351.         {
  352.         case 0:
  353.             c0++;
  354.             break;
  355.         case 1:
  356.             c1++;
  357.             break;
  358.         case 2:
  359.             c2++;
  360.             HealEdges (cp->edges[0], cp->edges[1]);
  361.             break;
  362.         default:
  363.             c3++;
  364.             break;
  365.         }
  366.     }
  367.     
  368. /*    qprintf ("%5i c0\n", c0); */
  369. /*    qprintf ("%5i c1\n", c1); */
  370. /*    qprintf ("%5i c2\n", c2); */
  371. /*    qprintf ("%5i c3+\n", c3); */
  372.     ShowTempEntry("%5i edges removed by tjunction", c2);
  373. }
  374.  
  375. /*
  376. ==============
  377. CountRealNumbers
  378. ==============
  379. */
  380. void CountRealNumbers (void)
  381. {
  382.     int        i;
  383.     int        c;
  384.     
  385.     ShowTempEntry("%5i regions", numfaces-firstmodelface);
  386.  
  387.     c = 0;
  388.     for (i=firstmodelface ; i<numfaces ; i++)
  389.         c += dfaces[i].numedges;
  390.     ShowTempEntry("%5i real marked surfaces", c);
  391.     
  392.     c = 0;
  393.     for (i=firstmodeledge ; i<numedges ; i++)
  394.         if (edgefaces[i][0])
  395.             c++;        /* not removed */
  396.  
  397.     ShowTempEntry("%5i real edges", c);
  398. }
  399.  
  400. /*============================================================================= */
  401.  
  402. /*
  403. ==============
  404. GrowNodeRegion_r
  405. ==============
  406. */
  407. void GrowNodeRegion_r (node_t *node)
  408. {
  409.     dface_t        *r;
  410.     face_t        *f;
  411.     int            i;
  412.  
  413.     if (node->planenum == PLANENUM_LEAF)
  414.         return;
  415.  
  416.     node->firstface = numfaces;
  417.  
  418.     for (f=node->faces ; f ; f=f->next)
  419.     {
  420. /*        if (f->outputnumber != -1) */
  421. /*            continue;    /* allready grown into an earlier region */
  422.             
  423.     /* emit a region */
  424.  
  425.         if (numfaces == MAX_MAP_FACES)
  426.             Error ("MAX_MAP_FACES");
  427.         f->outputnumber = numfaces;
  428.         r = &dfaces[numfaces];
  429.  
  430.         r->planenum = node->outputplanenum;
  431.         r->side = f->planeside;
  432.         r->texinfo = f->texturenum;
  433.         for (i=0 ; i<MAXLIGHTMAPS ; i++)
  434.             r->styles[i] = 255;
  435.         r->lightofs = -1;
  436.  
  437.     /* add the face and mergable neighbors to it */
  438.     
  439. #if 0
  440.         ClearRegionSize ();
  441.         AddFaceToRegionSize (f);
  442.         RecursiveGrowRegion (r, f);
  443. #endif
  444.         r->firstedge = firstedge = numsurfedges;
  445.         for (i=0 ; i<f->numpoints ; i++)
  446.         {
  447.             if (numsurfedges == MAX_MAP_SURFEDGES)
  448.                 Error ("numsurfedges == MAX_MAP_SURFEDGES");
  449.             dsurfedges[numsurfedges] = f->edges[i];
  450.             numsurfedges++;
  451.         }
  452.         
  453.         r->numedges = numsurfedges - r->firstedge;
  454.  
  455.         numfaces++;
  456.     }
  457.  
  458.     node->numfaces = numfaces - node->firstface;
  459.  
  460.     GrowNodeRegion_r (node->children[0]);
  461.     GrowNodeRegion_r (node->children[1]);
  462. }
  463.  
  464.  
  465. /*
  466. ==============
  467. GrowNodeRegions
  468. ==============
  469. */
  470. void GrowNodeRegions (node_t *headnode)
  471. {
  472.     ShowStatusEntry("Growing Node Regions.");
  473.         
  474.     GrowNodeRegion_r (headnode);
  475.         
  476. /*RemoveColinearEdges (); */
  477.     CountRealNumbers ();
  478. }
  479.  
  480. /*
  481. ===============================================================================
  482.  
  483. Turn the faces on a plane into optimal non-convex regions
  484. The edges may still be split later as a result of tjunctions
  485.  
  486. typedef struct
  487. {
  488.     vec3_t    dir;
  489.     vec3_t    origin;
  490.     vec3_t    p[2];
  491. } 
  492. for all faces
  493.     for all edges
  494.         for all edges so far
  495.             if overlap
  496.                 split
  497.                 
  498.  
  499. ===============================================================================
  500. */
  501.  
  502.  
  503.  
  504.  
  505.  
  506.  
  507.  
  508.  
  509.  
  510.  
  511.  
  512.  
  513.  
  514.